1. Field of the Invention
An Asynchronous Transfer Mode (henceforth ATM) network has switching points or "nodes" for transmission of data among senders and receivers connected to the network. The "switching" performed by these switching points is in fact the action of passing on a "cell" of data received by a switching point or node to a further node in the network. Such switching actions are the means by which communication data is moved through the ATM network.
The present invention relates to a method and apparatus for merging data received at a node from a number of senders in an ATM network.
The ATM system has a broadly accepted set of standards which ensure compatibility of ATM networks and their components. The book "Asynchronous Transfer Mode (ATM)-Technical Overview", by Harry J. R. Dutton and Peter Lenhard, 2nd Edition, published by Prentice Hall, ISBN 0-13-52044-5, can be consulted in order to gain familiarity with the ATM system.
The following explanations and descriptions help define the some basic characteristics of ATM communication:
All digital communication packets or "frames" are converted or segmented at a sender into cells (henceforth simply "cells"). These cells are transferred through the ATM network via a transmission medium. PA1 Each cell has a fixed data length. For example, in the ATM standard each cell consists of a 5-byte header and a 48-byte information field. One part of the header carries data which is termed a "Virtual Path Identifier" (henceforth the "VPI"). Another part of the header carries data termed a "Virtual Channel Identifier" (henceforth the "VCI"). PA1 The path to be followed by a cell through an ATM network is defined by a series of "look-up tables" which are typically contained in storage devices in the switching points or nodes of the network. These look-up tables contain routing information to be consulted when a cell arrives at the switch point. PA1 The ATM network has some switching points called "Virtual Channel Switches". A "Virtual Channel Link" is the link between two successive virtual channel switches in the ATM network. A "Virtual Channel Connection" (VCC) is a route through the ATM network consisting of a particular set of virtual channel links. An example of such a virtual channel connection is the route from the point of origin of a communication in the ATM network via two or more virtual channel links to the destination of the communication in the ATM network. It should be clearly understood that the virtual channel "connection" here refers to a route through the ATM network and not to the action of making a connection. PA1 The ATM network also has some switching points called "Virtual Path Switches". A "Virtual Path Link" is the link between two successive virtual path switches in the ATM network. There may be several virtual path switches within one virtual channel link. The "Virtual Path Connection" (VPC) is the route through several virtual path switches followed by a particular cell. PA1 1) Globally unique VCI mechanism for VP switching. PA1 2) VCI collision avoidance using VC switching. PA1 3) VCI collision resolution using VP-VC switching.
FIG. 1 (prior art) illustrates the parts of the header recognized as belonging to the VPI and VCI.
A switching action performed at a virtual channel switch in the ATM network is made in dependence on the data in both the VPI and VCI fields of the cell's header.
A switching action performed at a virtual path switch in the ATM network is made in dependence on only the data in the VPI field of the cell's header. In short, a VPI bundles several VCIS.
It may instructive for an accurate understanding of the current invention to review the function of the look-up tables stored at the switching points:
A cell, segmented from a frame originating at a sender, starts as its entry point into the ATM network with a certain value stored in the VPI data field in its header. When the cell reaches the first virtual path switch, this switch reads the VPI in the header.
The value of the VPI is now used either directly or indirectly as a key to derive the address located in the look-up table held in the storage of the virtual path switch. The data value found at that particular address in the look-up table is then put into the cell's header in place of the original VPI. The particular exit port from the virtual path switch out of which the cell is to be sent is also determined by a value stored at the same address in the look-up table. The cell is now sent from the first virtual path switch further through the ATM network, having had its VPI value changed by the virtual path switch. At each subsequent virtual path switch in the virtual path connection a similar switching action to this takes place, i.e. the value of the VPI in the cell on arrival at the switch is accessed in the look-up table, and the value stored in the look-up table under that address is inserted into the VPI data field in the cell's header prior to sending the cell further through the network. Thus the values stored in the look-up tables at the various switching points determine the cell's route through the ATM network.
Although the VPI value can be used as the address in the look-up table, other arrangements for finding a particular entry in the table may be contemplated. It is only important that the VPI value of the incoming cell reliably leads to the location of the stored information which tells the virtual path switch how to direct that cell to the next node within the ATM network.
By definition, all cells having the same incoming VPI are switched together at a virtual path switch, i.e. they are all sent on with the same outgoing VPI independently of their VCI value. Therefore several cells with different values of VCI may follow the same virtual path connection. Thus the virtual path connection can be considered to be effectively a bundle of virtual channel connections.
In general, there will be one particular look-up table in the virtual path switch for each input port to the switch. Therefore a cell arriving at the switch at one particular input port with one particular VPI value in its header will not necessarily be sent out on the same output port as a cell with the same VPI value which arrives at the same virtual path switch on a different input port.
The switching action performed at a virtual channel switch involves consulting a look-up table which has entries accessed according to the value of the VPI and VCI data fields together. Comparing the possible number of VP addresses (2**12=4096) and of VC addresses (2**16--65,536), it is obvious that a VC switch requires larger look-up tables and thus vastly more memory space as a VP switch in the same network.
There is in fact nothing in the ATM standard which prevents one switching point or node in the ATM network acting as both a virtual path switch and a virtual channel switch (i.e. as dual function nodes).
The ATM standards for the VPI and VCI are given in "CCITT Recommendations I. 361 and 363".
ATM switching technology is also disclosed in numerous patents and patent applications. U.S. Pat. No. 5,239,537 for example describes means and methods to substitute a corrupted VP by an alternate VP. The U.S. Pat. No. 5,271,010 to Miyake describes a converter for converting the VPI and a VCI, i.e., the full 28 bit address attached to the header of an ATM cell.
2. Description of the Prior Art
There have been several recent submissions describing schemes for merging ATM traffic from multiple senders on a single ATM node or connection point.
ATM Forum draft 97-xxxx, 1997 entitled "Support for Routers in an ATM Network", by Douglas Dykeman et al., describes the use of merged connections to support routing in ATM networks.
Merging requires a method to insure that cells from different senders can be properly reassembled into frames at the receiver. As suggested in ATM Forum draft 97-0261, 1997, entitled "Multipoint to Point Vcs", by Juha Heinanen, a key environment for such merged connections is AAL5/UBR. As will be understood by those skilled in the art, AAL5 is a network service class of ATM Adaptation Layer (AAL), while UBR refers to a best effort level of service where data can be discarded if congestion is encountered.
Merge Alternatives Overview Merge schemes can be broadly classed as Frame-Based or Cell-Based. In the case of Frame-Based Merge cells associated with a frame are transmitted contiguously on outbound links. The function of collecting cells for contiguous transmission may be called "pseudo-reassembly", as full AAL5 reassembly is not required. Frame-based merge offers the advantage that a merged connection appears no different than a non-merged connection from the perspective of senders and receivers. Frame-Based Merge requires modification of the switch to perform pseudo-reassembly and sufficient memory to buffer frames undergoing reassembly. It also introduces latency (the delay between transmission by the sender and receipt by the receiver) greater than that associated with cell relay.
In the case of Cell-Based Merge, cells associated with frames from different senders are interleaved &lt;on links&gt; at switching nodes. An identifier is required so that cells from different senders can be distinguished and reassembled into frames at the receiver. If, for example, traffic is merged on a VP connection point, a globally unique VCI value associated with each sender can be used to distinguish cells for reassembly at the receiver.
Cell-Based schemes can be further classed as static or dynamic. In static schemes, the assignment of the identifier used to distinguish cells from different senders is relatively long-lived. The assignment can be made by manual definition, distributed assignment protocol, signaling, or other means. In dynamic schemes, the identifier assignment is short-lived. In particular, a new assignment can be made for each individual frame.
Before describing the Dynamic Cell-Based Merge approach of the present invention, it is useful to review alternatives for Static Cell-Based Merge. Three alternatives are described in ATM Forum draft 97-0379, 1997, entitled "Distributed Mechanisms for VCI in VP-Based Multicast", by R. Venkateswaran et al:
In the first alternative, the sender identifier is a globally unique VCI. This value can be assigned by a central server or by individual merge &lt;points&gt; connection nodes. In the latter case, the VCI space is partitioned among the &lt;Merge Points&gt; nodes. A key advantage of this scheme is that no VC resources are required in the switching nodes as only VP switching is performed. The disadvantages are necessity for a global VCI uniqueness' protocol and a limitation of 4096 on the number of VP merged connections passing through any switch (assuming the full 12-bits of VP are used). Also switches often support some form of Early Packet Discard for UBR traffic; such schemes may not work when there is no VC awareness in switches.
The second alternative avoids the requirement for globally unique identifiers by using locally unique VCI values and performing VC switching. Conceptually, there is a distinct VC from each sender to the receiver. The advantage of this scheme is that no protocol is necessary to insure global uniqueness of the identifier. Also, any traffic management performed by the switch for VC connections, will continue to work in this environment. One disadvantage of this scheme is that a sender cannot send data until signaling to establish the VC has completed. This can be contrasted to the VP switching alternative where a new sender can send data on the VP connection simply by using the unique VCI assigned to it. The authors suggest that this problem can be relieved to some extent by using controls cells to establish VC entries. A more significant disadvantage of the second scheme is the requirement for a VC table entry for each sender on a merged connection. In an environment with N receivers and N senders, a switch would require on the order of N**2 VCI table entries. Switches often have significant limitations on the number of such entries.
The third alternative is a hybrid of the first two. VP Switching is used but there is no attempt to insure that the VCI is globally unique. Instead, there is a mechanism for a merge node or point to detect that two senders using that merge point are using the same VCI value. When this collision is observed, the VC switching alternative is used on the path from the detecting merge point to the receiver.